package com.Oct_Four;

import java.util.Arrays;

public class Solution52 {

    int ans;

    public int totalNQueens(int n) {
        ans=0;
        char[][] chessboard=new char[n][n];
        for (char[] c:chessboard)
        {
            Arrays.fill(c,'.');
        }
        backtracking(n,0,chessboard);
        return ans;
    }

    void backtracking(int n,int row,char[][] chessboard){
        if (row==n)
        {
            ans++;
            return;
        }
        for (int col=0;col<n;col++)
        {
            if (isValid(row,col,chessboard,n))
            {
                chessboard[row][col]='Q';
                backtracking(n,row+1,chessboard);
                chessboard[row][col]='.';
            }
        }
    }

    private boolean isValid(int row,int col,char[][] chessboard,int n){
        for (int i=0;i<row;i++)
        {
            if (chessboard[i][col]=='Q')
            {
                return false;
            }
        }
        for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if (chessboard[i][j]=='Q') return false;
        }
        for (int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if (chessboard[i][j]=='Q') return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution52 solution52=new Solution52();
        System.out.println(solution52.totalNQueens(1));
    }
}
